设有一个 $01$ 序列 $s$. 记

• $L$ 是 $s$ 的最长不降子序列的长度,
• $S$ 为 $s$ 中 $1$ 的个数,
• $T = max_i (\text{$s[1 \dots i]$ 里 $0$ 的个数减 $1$ 的个数})$.

那么 $L=S+T$, 因为 $$L = max_i (\text{$s[1 \dots i]$ 中 $0$ 的个数} + \text{$s[i+1\dots n]$中$1$的个数}).$$

所以按线性性 $E(L)=E(S)+E(T)$, 显然 $E(S)=n/2$, 因此只需要计算$E(T)$.

显然 $T≥0$, 因为可以取$i=0$. 考虑 $T\geq k$ 的方案数. 这就相当于在平面上, 从 $(0,0)$ 出发, 每次可以往右上或者右下走一步, 问走 $n$ 步途中至少碰到一次水平线 $y=k$ 的方案数. 那么有两种可能：

• 最终落点的 $y \geq k$. 这部分贡献是 $\sum_{2a \leq n-k} \binom{n}{a}$, $a$ 是枚举往右下走的步数.
• 最终落点的 $y < k$. 根据反射法这等于从 $(2k,0)$ 出发走 $n$ 步最终到达 $y < k$ 位置的方案数, 是 $\sum_{2a < n-k} \binom{n}{a}$, $a$ 是枚举往右上走的步数.

因此 $T \geq k$ 的概率是上面两个式子加起来除以 $2^n$.

所以 $T$ 的期望是 $$\begin{aligned} &\sum_{k=1}^n P(T \geq k) \\ =& \frac{1}{2^n} \sum_{k=1}^n \left( \sum_{2a \leq n-k} \binom{n}{a} + \sum_{2a < n-k} \binom{n}{a} \right) \\ =& \frac{1}{2^n} \sum_{a=0}^{\lfloor (n-1)/2 \rfloor} \binom{n}{a} (2n-4a-1) \\ \end{aligned}$$

显然这是个整式递推, 可以 $O(n)$ 计算. 事实上设 $A_n$ 是 $T$ 的期望, 那么

$$A_{2n} - A_{2n-1} = A_{2n+1} - A_{2n} = \frac14 + \frac{1}{2^{2n+2}}\binom{2n}{n}.$$